public class First {
    //最长回文字串 动态规划
//    public static String longestPalindrome(String s) {
//        if (s == null || s.length() < 2) {
//            return s;
//        }
//        int strLen = s.length();
//        int maxStart = 0;  //最长回文串的起点
//        int maxEnd = 0;    //最长回文串的终点
//        int maxLen = 1;  //最长回文串的长度
//
//        boolean[][] dp = new boolean[strLen][strLen];
//
//
//        for (int r = 1; r < strLen; r++) {
//            for (int l = 0; l < r; l++) {
//                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
//                    dp[l][r] = true;
//                    if (r - l + 1 > maxLen) {
//                        maxLen = r - l + 1;
//                        maxStart = l;
//                        maxEnd = r;
//
//                    }
//                }
//
//            }
//
//        }
//        return s.substring(maxStart, maxEnd + 1);
//
//    }
//    public static void main(String[] args) {
//        long start=System.currentTimeMillis();
//        longestPalindrome("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee" +
//                "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee" +
//                "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee" +
//                "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee" +
//                "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee" +
//                "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee" +
//                "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee" +
//                "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee" +
//                "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee" +
//                "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee");
//        long end=System.currentTimeMillis();
//        System.out.println(end-start);
//    }

    //最小路径

//        public static int minPathSum(int[][] grid) {
//            // Note: The Solution object is instantiated only once and is reused by each test case.
//            int rowL = grid.length;
//            int rL = grid.length;
//            int cL = grid[0].length;
//            int[] minArr = new int[cL];
//            for(int i=0; i<minArr.length; i++){
//                minArr[i] = Integer.MAX_VALUE;
//            }
//            minArr[0] = 0;
//// 		for(int j = 1; j<cL; j++){
//// 			minArr[j] += minArr[j-1];
//// 		}
//            for(int i=0 ; i<rL; i++){
//                minArr[0] += grid[i][0];
//                for(int j = 1; j<cL; j++ ){
//                    minArr[j] = Math.min(minArr[j], minArr[j-1]) + grid[i][j];
//                }
//            }
//            return minArr[cL - 1];
//        }

//    public static int minPathSum(int[][] grid) {
//        int i;
//        int j=0;
//        for(i=0;i<grid.length;i++){
//            for(j=0;j<grid[i].length;j++){
//                if(i==0&&j==0){
//                    continue;
//                }else if(i==0){
//                    grid[i][j]+=grid[i][j-1];
//                }else if(j==0){
//                    grid[i][j]+=grid[i-1][j];
//                }else{
//                    grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);
//                }
//            }
//        }
//
//        return grid[i-1][j-1];
//    }

//    public static void main(String[] args) {
//        int [][]grid={{1,3,1},{1,5,1},{4,2,1}};
//        int i = minPathSum(grid);
//        System.out.println(i);
//
//    }


}
